package _binary_search;

/**
 * 1351. 统计有序矩阵中的负数
 */
public class No1351 {
    /**
     * 1.闭区间
     */
    public int countNegatives1(int[][] grid) {
        int answer = 0;
        int n = grid[0].length;
        for (int[] g : grid) {
            int left = 0, right = n - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (g[mid] >= 0) left = mid + 1;
                else right = mid - 1;
            }
            answer += n - left;
        }
        return answer;
    }

    /**
     * 2.左闭右开
     */
    public int countNegatives2(int[][] grid) {
        int answer = 0;
        int n = grid[0].length;
        for (int[] g : grid) {
            int left = 0, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (g[mid] >= 0) left = mid + 1;
                else right = mid;
            }
            answer += n - left;
        }
        return answer;
    }

    /**
     * 3.开区间
     */
    public int countNegatives3(int[][] grid) {
        int answer = 0;
        int n = grid[0].length;
        for (int[] g : grid) {
            int left = -1, right = n;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (g[mid] >= 0) left = mid;
                else right = mid;
            }
            answer += n - right;
        }
        return answer;
    }
}
